package leetcode.code0907;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution1 extends Solution907 {

	private int mod = (int) 1e9 + 7;

	@Override
	public int sumSubarrayMins(int[] arr) {
		int len = arr.length;
		if (len == 1)
			return arr[0];
		Stack<List<Integer>> s = new Stack<>();
		long ans = 0;
		for (int i = 0; i < len; i++) {
			while (!s.isEmpty() && arr[s.peek().get(0)] > arr[i]) {
				List<Integer> maxList = s.pop();
				int rangeRight = i;
				int rangeLeft = s.isEmpty() ? -1 : s.peek().get(s.peek().size() - 1);
				int num = arr[maxList.get(0)];// 栈顶数字
				for (Integer index : maxList) {
					long r = subArrayNum(rangeLeft, index, rangeRight);
					for (int m = 0; m < r; m++) {
						ans += num;
						ans %= mod;
					}
				}
			}
			if (!s.isEmpty() && arr[s.peek().get(0)] == arr[i]) {
				s.peek().add(i);
			} else {
				List<Integer> list = new ArrayList<>();
				list.add(i);
				s.add(list);
			}
		}
		while (!s.isEmpty()) {
			List<Integer> maxList = s.pop();
			int rangeRight = len;
			int rangeLeft = s.isEmpty() ? -1 : s.peek().get(s.peek().size() - 1);
			int num = arr[maxList.get(0)];// 栈顶数字
			for (Integer index : maxList) {
				long r = subArrayNum(rangeLeft, index, rangeRight);
				for (int m = 0; m < r; m++) {
					ans += num;
					ans %= mod;
				}
			}
		}
		return (int) ans;
	}

	private long subArrayNum(int rangeLeft, Integer index, int rangeRight) {
		int left = index - rangeLeft - 1;
		int right = rangeRight - index - 1;
		return left * right + left + right + 1;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
//		so.debug2();
		so.debug3();

	}

}
